package com.剑指offer.第八章树;

/**
 * 使用前序遍历
 * <p>
 * 单纯的使用前序遍历，会有一个问题 并不知道 哪个节点是左节点 还是右节点,导致反序列化失败
 * <p>
 * 序列化时，我们将null的节点 序列化成 #
 */
public class 序列化和反序列化二叉树 {

    public String serialize(TreeNode treeNode) {
        if (treeNode == null) {
            return "#";
        }
        String value = String.valueOf(treeNode.val);
        String left = serialize(treeNode.left);
        String right = serialize(treeNode.right);
        return value + "," + left + "," + right;
    }

    public TreeNode deserialize(String nodeStr) {
        String[] split = nodeStr.split(",");
        int[] num = {0};
        return dfs(split, num);
    }

    /**
     * 6 # 6 # #
     *
     * @param split
     * @param num
     * @return
     */
    public TreeNode dfs(String[] split, int[] num) {
        String val = split[num[0]];
        num[0]++;
        if (val.equals("#")) {
            return null;
        }
        TreeNode treeNode = new TreeNode();
        treeNode.val = Integer.valueOf(val);
        treeNode.left = dfs(split, num);
        treeNode.right = dfs(split, num);
        return treeNode;
    }

}
